package com.example.system.class04;

/**
 * @Date 2022/7/19
 * @Created by Jonathan
 */
public class Code01_LinkReverse {


    static class Link {

        // 定义Node
        static class Node {
            Node next;
            int value;

            public Node(int value) {
                this.value = value;
            }

            @Override
            public String toString() {
                return "Node[" +
                        "" + value +
                        ']';
            }
        }

        // 创建链表  返回头结点
        public Node create(int[] arr) {
            Node head = null;
            if (arr == null || arr.length == 0) {
                return null;
            }
            // 初始化头结点
            head = new Node(arr[0]);
            Node cur = head;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new Node(arr[i]);
                cur = cur.next;
            }
            return head;
        }

        public void print(Node head) {
            Node cur = head;
            while (cur != null) {
                System.out.print(cur.value);
                cur = cur.next;
                // 下一个节点不为null才打印 ->
                if (cur != null) {
                    System.out.print("->");
                }
            }
            System.out.println();
        }


        public Node reverseList(Node cur) {
            if (cur == null || cur.next == null) {
                return cur;
            }

            // 通过这一步将当前节点的下一个接点返回
            Node newHead = reverseList(cur.next);
            // 当前节点的下一个节点的下一个节点指向当前节点
            // 就反转过来了 此时当前节点就相当于是尾结点
            // 这个“尾结点”还指向着下一个接点 还需要断掉
            cur.next.next = cur;
            cur.next = null;
            return newHead;
        }


        public Node reverse(Node head) {
            if (head == null || head.next == null) {
                return head;
            }
            if (head.next.next == null) {
                // reverse
                Node cur = head.next;
                cur.next = head;
                head.next = null;
                // return
                return cur;
            }

            // 到这个地方说明至少三个节点
            Node pre = head;
            Node cur = head.next;
            Node next = head.next.next;

            while (next != null) {
                cur.next = pre;
                pre = cur;
                cur = next;
                next = next.next;
            }
            // 跳出while循环之后 cur 就是最后一个节点
            // cur之前的都已经旋转过来了 将最后一次连接上即可
            cur.next = pre;
            // reverse之后的 尾巴指向倒数第二个节点  需要断掉 不然有死循环在里面
            head.next = null;
            return cur;
        }


        //
        public Node process(Node cur) {
            // base case
            if (cur == null || cur.next == null) {
                // 说明这是最后一个节点
                return cur;
            }
            // last 头结点
            Node last = process(cur.next);
            // 说明这是原来的头结点
            cur.next.next = cur;
            // 置为null
            cur.next = null;
            // 把头结点返回回去
            return last;
        }

        // 删除值为value的节点
        // todo
        public Node removeValue(Node head, int value) {


            return null;
        }

        public Node testRemoveValue(Node head, int value) {

            return null;
        }
    }


    public static void main(String[] args) {
        final Link link = new Link();
        int[] arr = new int[]{1, 2, 3, 4, 5, 6};
        final Link.Node head = link.create(arr);
        link.print(head);
        final Link.Node process = link.process(head);
        link.print(process);
        final Link.Node reverse = link.reverse(process);
        link.print(reverse);
        Link.Node reverseList = link.reverseList(reverse);
        link.print(reverseList);

    }
}
